/*
 * @lc app=leetcode.cn id=907 lang=typescript
 *
 * [907] 子数组的最小值之和
 */

// @lc code=start
function sumSubarrayMins(arr: number[]): number {
  // rmq(X,1)+...+rmq(x,n)
  const m = arr.length;
  const sum = new Array(m + 1).fill(0);
  const stack: number[] = [];
  let ans = 0;
  for (let i = 0; i < m; i++) {
    while (stack.length && arr[i] <= arr[stack[stack.length - 1]]) {
      stack.pop();
    }
    // 比当前元素小的上一个位置
    let pre = stack.length ? stack[stack.length - 1] : -1;
    stack.push(i);
    // 当前元素贡献的次数=比当前元素小的上一个元素贡献的次数+当前元素最小的区间跨度*当前元素
    sum[stack.length] = sum[stack.length - 1] + arr[i] * (i - pre);
    // 累加结果
    ans += sum[stack.length];
    ans %= 1e9 + 7;
  }

  return ans;
}
// @lc code=end
